package leetcode;

import com.sun.javafx.geom.Edge;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class CloneGraph {

    public static void main(String[] args) {
        CloneGraph object = new CloneGraph();
        Integer[][] array = {{2, 4}, {1, 3}, {2, 4}, {1, 3}};
        Node[] nodes = new Node[array.length];
        for (int i = 0; i < array.length; i++) {
            nodes[i] = new Node(i + 1);
        }
        for (int i = 0; i < array.length; i++) {
            List<Integer> nodeIndex = Arrays.asList(array[i]);
            ArrayList<Node> node = new ArrayList<>();
            for (int j = 0; j < nodeIndex.size(); j++) {
                node.add(nodes[nodeIndex.get(j) - 1]);
            }
            nodes[i].neighbors = node;
        }
        object.printGraph(nodes[0]);
        System.out.println("*******");
        Node res = object.cloneGraph(nodes[0]);
        object.printGraph(res);

    }

    public void printGraph(Node node) {
        if (node == null) {
            return;
        }
        HashSet<Edge> edges = new HashSet<>();
        printGraph(node, edges);
    }

    public void printGraph(Node node, HashSet<Edge> edge) {
        if (node == null) {
            return;
        }
        System.out.println("node"  + node.val + "------");
        if (node.neighbors == null || node.neighbors.size() == 0) {
            System.out.println("neighbors is null");
            return;
        }
        for (int i = 0; i < node.neighbors.size(); i++) {
            System.out.println(node.neighbors.get(i).val);
        }
        for (int i = 0; i < node.neighbors.size(); i++) {
            if (edge.add(new Edge(node.val, node.neighbors.get(i).val))) {
                System.out.println(Arrays.toString(edge.toArray()));
                printGraph(node.neighbors.get(i), edge);
            }
        }
    }

    public void printGraph(Node[] node) {
        if (node == null) {
            return;
        }
        for (int i = 0; i < node.length; i++) {
            System.out.println("node"  + (i + 1) + "------");
            for (int j = 0; j < node[i].neighbors.size(); j++) {
                System.out.println(node[i].neighbors.get(j).val);
            }
        }
    }


    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        HashMap<Integer, Node> map = new HashMap<>();
        return cloneGraph(node, map);
    }

    public Node cloneGraph(Node node, HashMap<Integer, Node> map) {
        if (node == null) {
            return null;
        }
        System.out.println("node.val " + node.val);
        Node res = new Node(node.val);
        if (node.neighbors == null) {
            return res;
        }
        map.put(node.val, res);
        for (int i = 0; i < node.neighbors.size(); i++) {
            Node cur;
            if ((cur = map.get(node.neighbors.get(i).val)) == null) {
                cur = cloneGraph(node.neighbors.get(i), map);
            }
            res.neighbors.add(cur);
        }
        return res;
    }

    static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    static final class Edge {
        public int vertex1;
        public int vertex2;
        public int type = 0;

        Edge(int vertex1, int vertex2) {
            this.vertex1 = vertex1;
            this.vertex2 = vertex2;
        }

        Edge(int vertex1, int vertex2, int type) {
            this.vertex1 = vertex1;
            this.vertex2 = vertex2;
            this.type = type;
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Edge)) {
                return false;
            }
            Edge edge = (Edge) obj;
            boolean isSame = (this.vertex1 == edge.vertex1 && this.vertex2 == edge.vertex2);
            boolean revert = (this.vertex1 == edge.vertex2 && this.vertex2 == edge.vertex1);
            if (type == 0) {
                return isSame || revert;
            } else {
                return isSame;
            }
        }

        @Override
        public int hashCode() {
            if (type == 0) {
                return Integer.valueOf(vertex1).hashCode() + Integer.valueOf(vertex2).hashCode();
            } else {
                return Integer.valueOf(vertex1).hashCode() * 13 + Integer.valueOf(vertex2).hashCode();
            }
        }

        @Override
        public String toString() {
            return "<" + vertex1 + "," + vertex2 + ">";
        }
    }
}
